package com.hy;

/**
 * Created With IntelliJ IDEA.
 * Descriptions:找到最长的半重复子字符串
 *
 * 给你一个下标从 0 开始的字符串 s ，这个字符串只包含 0 到 9 的数字字符。
 * 如果一个字符串 t 中至多有一对相邻字符是相等的，那么称这个字符串 t 是 半重复的 。例如，0010 、002020 、0123 、2002 和 54944 是半重复字符串，而 00101022 和 1101234883 不是。
 * 请你返回 s 中最长 半重复 子字符串的长度。
 * 一个 子字符串 是一个字符串中一段连续 非空 的字符。
 *
 * 示例 1：
 * 输入：s = "52233"
 * 输出：4
 * 解释：最长半重复子字符串是 "5223" ，子字符串从 i = 0 开始，在 j = 3 处结束。
 *
 * 示例 2：
 * 输入：s = "5494"
 * 输出：4
 * 解释：s 就是一个半重复字符串，所以答案为 4 。
 *
 * 示例 3：
 * 输入：s = "1111111"
 * 输出：2
 * 解释：最长半重复子字符串是 "11" ，子字符串从 i = 0 开始，在 j = 1 处结束。
 *
 * 提示：
 * 1 <= s.length <= 50
 * '0' <= s[i] <= '9'
 * <p>
 * User:Mr.Du
 * Date:2024/3/29
 * Time:15:31
 */
public class LongestSemiRepetitiveSubstring {
    /**
     * 计算字符串中最长的半重复子字符串的长度。
     * 半重复子字符串是指一个字符串，它能够被分成两个非空部分，这两个部分都是该字符串的子串，但它们在字符串中的相对顺序是颠倒的。
     *
     * @param s 输入的字符串
     * @return 返回最长的半重复子字符串的长度
     */
    public int longestSemiRepetitiveSubstring(String s) {
        int n = s.length(); // 字符串的长度
        if(n == 1) return 1; // 如果字符串长度为1，则直接返回1
        int l = 0, r = 0, res = 0, cnt = 0; // l左指针，r右指针，res当前最长半重复子字符串长度，cnt计数器

        // 遍历字符串寻找最长的半重复子字符串
        while(r < n - 1){
            if(s.charAt(r) == s.charAt(r+1)){ // 如果当前字符和下一个字符相同，增加计数器
                cnt++;
            }
            // 当计数器大于1时，向右移动左指针，直到计数器等于1
            while(cnt > 1){
                if(s.charAt(l) == s.charAt(l+1)){
                    cnt--;
                }
                l++;
            }
            r++; // 右指针右移
            res = Math.max(res, r - l + 1); // 更新最长半重复子字符串长度
        }
        // 如果最长半重复子字符串长度为1，返回2，否则返回最长半重复子字符串长度
        return res;
    }
}
